-- pb 18
module Main where

import Control.Monad.State
import Char
import Data.List 

parseNodes :: String -> [Integer]
parseNodes = map readInteger . words

readInteger :: String -> Integer
readInteger  = toInteger . foldl (\s x -> digitToInt x + s * 10) 0 

-- reduces a graph into a singleton
-- first the bottom row is compressed then it's summed with the 
-- row above
reduce :: [[Integer]] -> Integer
reduce  = head . (foldl1 fun) where
    fun xs ys = zipWith (+) (compress xs) ys

-- compress an array: compares elements 2 by 2 and delete the smaller one
compress :: [Integer] -> [Integer]
compress xs = zipWith max (tail xs) xs
-- a state monad which build the nodes then reduce them         
reducer :: StateT [[Integer]] IO Integer
reducer = do
  nodes <- get
  str <- lift $ catch getLine (const $ return "")
  if str == "" then return $ reduce nodes else 
        modify ((parseNodes str) :) >> reducer
-- the nil state
nilSt = [] :: [[Integer]]
-- the main
main = evalStateT reducer nilSt >>= print
